package org.example;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Test3 {
    public String longestWord(String[] words) {
        Arrays.sort(words);
        int n = words.length;
        boolean[] dp = new boolean[n];
        String ret = "";
        for (int i = 0; i < n; i++) {
            String prev = words[i].substring(0,words[i].length()-1);
            if (prev.equals("") || (i > 0 && dp[i-1] && ((prev.equals(words[i-1])
                    || prev.equals(words[i-1].substring(0,words[i-1].length()-1)))))) {
                dp[i] = true;
                if (words[i].length() > ret.length()) {
                    ret = words[i];
                }else if (words[i].length() == ret.length()) {
                    ret = words[i].compareTo(ret) < 0 ? words[i] : ret;
                }
            }
        }
        return ret;
    }

    public String longestWord2(String[] words) {
        Arrays.sort(words);
        Set<String> set = new HashSet<>();
        set.add("");
        String ret = "";
        for (int i = 0; i < words.length; i++) {
            String prev = words[i].substring(0,words[i].length()-1);
            if (set.contains(prev)) {
                set.add(words[i]);
                if (prev.length() + 1 > ret.length()) {
                    ret = words[i];
                }else if (prev.length() + 1 == ret.length()) {
                    ret = words[i].compareTo(ret) < 0 ? words[i] : ret;
                }
            }
        }
        return ret;
    }

    public String longestWord1(String[] words) {
        Set<String> set = new HashSet<>();
        set.add("");
        String ret = words[0];
        for (String word : words) {
            set.add(word);
        }
        for (String word : words) {
            if (!set.contains(word.substring(0,word.length()-1))) set.remove(word);
        }
        for (String word : words) {
            String prev = word.substring(0,word.length()-1);
            if (set.contains(prev)) {
                if (word.length() > ret.length()) {
                    ret = word;
                }else if (word.length() == ret.length()) {
                    ret = word.compareTo(ret) < 0 ? word : ret;
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        String[] words1 = {"ogz","eyj","e","ey","hmn","v","hm","ogznkb","ogzn","hmnm","eyjuo","vuq","ogznk","og","eyjuoi","d"};
        String[] words = {"rac","rs","ra","on","r","otif","o","onpdu","rsf","rs","ot","oti","racy","onpd"};
        Test3 test3 = new Test3();
        System.out.println(test3.longestWord(words));
        System.out.println(555);
    }
}
